/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q2537.java
 * @Author : WangRuoyu
 * @Date 2023/1/28 11:02
 */

package leetcode;

// TODO
public class Q2537 {
    public long countGood(int[] nums, int k) {
        if (nums.length == 1) {
            return 0;
        } else if (nums.length == 2) {
            if ((nums[0] == nums[1]) && k == 1) {
                return 1;
            }
            return 0;
        } else {
            int len = nums.length;
            long[][] dp = new long[len][len];
            long res = 0;

            for (int j = 1; j < len; j++) {
                for (int i = j - 1; i >= 0; i--) {
                    int tmp = 0;
                    for (int l = i; l <= j - 1; l++) {
                        if (nums[l] == nums[j]) {
                            tmp++;
                        }
                    }
                    dp[i][j] = tmp + dp[i][j - 1];
                    tmp = 0;
                    for (int l = i + 1; l <= j; l++) {
                        if (nums[l] == nums[i]) {
                            tmp++;
                        }
                    }
                    dp[i][j] = Math.max(tmp + dp[i + 1][j], dp[i][j]);
                    if (dp[i][j] >= k) {
                        res++;
                    }
                }
            }

            return res;
        }
    }

    public static void main(String[] args) {
        Q2537 sl = new Q2537();
        int[] nums = {3, 1, 4, 3, 2, 2, 4};
        int k = 10;
//        int[] nums = {1, 1, 1, 1, 1};
//        int k = 10;
        System.out.println(sl.countGood(nums, k));
    }
}